1. Field of the Invention
The present invention relates to a blind watermarking method by grouping codewords for VQ-quantized images and, more specifically, to a watermark insertion method in which a codebook is divided into three groups satisfying specific standards and a codeword is allocated based on the group to which the corresponding codeword belongs so as to insert watermark information, and a watermark extraction method for extracting the watermark inserted by the watermark insertion method.
2. Background of the Related Art
A watermarking technique that inserts data into digital contents to protect the copyright thereof is being studied and developed in various ways according to the kind of digital media (image, audio, video, 2D/3D graphic, etc.), compression/decompression methods (DCT [Cox 1997], DFT [Ruanaidh 1996], DWT [Niu 2000], VQ [Lu 2000] and so on), and utilizing methods (visible/invisible, durable/destructive, open/not-open to the public, etc.).
In the meantime, a vector quantization (VQ) technique is an approximation solution frequently used for image compression and consists of three-step processes. Specifically, the first step (learning stage) generates a codebook (c0, c1, . . . , cN−1) consisting of N vectors from a set of input vectors for learning. The second step (compression step) represents a source image X to be compressed as T vectors (x0, x1, . . . , xT−1). In addition, for each input vector xt(0≦t≦T−1), the second step finds out a codeword ci that is the most similar to the input vector from the codebook and allocates i instead of xt. The third step (decompression step) extracts ci corresponding to i from the codebook to use it in place of xt.
An example of compression/decompression of an image using a codebook composed of eight codewords (c0, . . . , c7) will be explained with reference to FIG. 1.
FIG. 1 is a diagrammatic view illustrating compression/decompression processes in vector quantization.
Referring to FIG. 1, at the compression step, first, the image to be compressed is decomposed into vectors of the same dimension as the codewords, the vectors (x0, x1, x2, . . . ) are compared with the codewords to select the codeword closest to each vector, and the position of the closest codeword is used in the compressed image. That is, codewords c3, c1 and c6 are judged to be the closest to x0, x1 and x2, respectively, and 3, 6 and 1 representing the positions of the closest codewords are used in the compressed image. At the decompression step, codewords are extracted from the codebook with the position values of the codewords, stored in the compressed image, to generate a restoration image similar to the original image. As described above, the vector quantization enables efficient compression and rapidly restores images.
While the vector quantization technique is the approximation solution frequently used for image compression, a watermarking technique based on vector quantization has not being sufficiently studied, compared with the fruitful result of the watermarking technique in a spatial area or conversion area.
The VQ-based watermarking technique proposed by Lu and Sun in 2000 classifies similar codewords contained in a codebook to form multiple groups (group size is 2n where n=0, 1, . . . ) and confirms the codeword that is the most similar to each input image vector and the group including this codeword. The number of bits of watermark capable of being inserted is determined according to the set group size 2n.
An example using the VQ-based watermarking technique proposed by Lu and Sun will be described with reference to FIG. 2. In this example, eight codewords are classified into four groups {c0,c3}, {c2}, {c6} and {c1,c4,c5,c7}.
c3 that is the most similar to the input vector x0 is included in the first group. A 1-bit watermark can be inserted into the first group because this group includes two codewords. That is, the codewords are used without any change when the watermark bit value is 0 but they are replaced by other codewords when the bit value is 1. Because the bit value to be inserted is 1, c0 can be used instead of c3. Though the input vector x1 is the most similar to c6, the third group includes only this codeword so that watermark cannot be inserted into this group.
Since the fourth group includes four codewords, a 2-bit watermark can be inserted into this group. In case of the input vector x2, c1 is replaced by c7 in order to insert the 2-bit watermark (11) into the fourth group. In the extraction process, 3 that is the group's inner distance between c1 and c7 is represented in bits so as to extract watermark information.
The above-described VQ-based watermarking technique by Lu and Sun maximizes the quantity of information of watermark inserted. However, this technique has the problem in that the quantity of lost watermark information is increased or loss of watermark information may be concentrated on one spot when a compressed image is damaged because the quantity of information inserted by input vectors is intensively varied. Furthermore, it is difficult to use the technique since the extraction process indispensably requires the original image.